| 经典的进程同步问题 | 您所在的位置：网站首页 › 磁盘 临界资源 › 经典的进程同步问题 |
经典的进程同步问题
|
经典的进程同步问题-----生产者-消费者问题详解
本文和接下来几篇博文是对上篇文章（进程同步机制）的一次实践，通过具体的例子来加深理论的理解，会用三个经典的进程同步问题来进行讲解，并且会配有伪代码和Java实践（使用多线程模拟），深入的进行讲解。 进程同步问题是一个非常重要且相当有趣的问题，因而吸引了很多学者对他进行研究，比如在前几篇博客中提到的老熟人迪杰斯特拉，由此也产生了一系列经典的进程同步问题，本文就选取其中较为代表性的生产者-消费者问题来进行学习，以帮助我们更好的理解进程同步的概念及实现方法。 生产者-消费者问题是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此该问题有很大的代表性及实用价值。并且现在很多技术都使用到了，最典型的就是消息队列。 本文主要是对经典进程同步问题的求解，因此在这里先给出一个解题思路（仅代表个人意见、如有疑问，可评论区讨论）： 分析清楚题目涉及的进程间制约关系；设置信号量（包括信号量的个数和初值，写出信号量物理含义）；给出进程相应程序的算法描述或流程控制，并把P、V操作加到程序适当之处。 1.问题描述 有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费。为了使生产这进程与消费者进程能并发的执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将其生产的产品放到一个缓冲区（缓冲池中的一个存储单位）中；消费者进程可从一个缓冲区中取走产品去消费。 需要注意的是，尽管所有的生产者和消费者都是以异步的方式运行的，但是他们之间必须保持同步，既不允许消费者进程在缓冲区为空时去取产品，也不允许生产者进程在缓冲区已满且产品尚未被取走时向缓冲区投放产品。 
2.问题分析
缓冲池一次只能有一个进程访问；只要缓冲池未满，生产者就可以把产品送入缓冲区；只要缓冲池未空，消费者就可以从缓冲区中取走产品。
下图是一个生产者与消费者进程执行的流程图，从图中我们可以很清晰的看到上述的三个进程间的关系，其中生产者和消费者中操作缓冲区都需要先进行申请，也就是我们说的进入区，操作完成后要执行释放，也就是退出区，通过这样来实现对缓冲池的互斥访问。通过图中的贯通两个进程的虚线来实现生产者和消费者的同步关系。 
3.信号量设置
由于有界缓冲池是一个临界资源，必须互斥使用，这时可以利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。因为是互斥信号量，所以mutex初值为１。 另外，可以设置两个同步信号量：一个表示缓冲池中空缓冲区的数目，用empty表示，初值为缓冲池的大小n；另一个表示已满缓冲区的数目，即缓冲池中消息的数量，用full表示，初值为０。 除了信号量外，我们可以使用循环链表来表示有界缓冲池，假设缓冲池的大小为n，我们用buffer[n]来表示，另外还有两个队首指针in和队尾指针out，其初值都为0。 4.记录型信号量解决生产者-消费者问题 首先我们先使用记录型信号量来解决生产者-消费者问题，根据上面的分析，我们先给出伪代码： int in=0,out=0; //item为消息的结构体 item buffer[n]; semaphore mutex=1,empty=n,full=0; //初始化信号量 void producer(){ do { //生产者产生一条消息 producer an item nextp; ... //判断缓冲池中是否仍有空闲的缓冲区 P(empty); //判断是否可以进入临界区（操作缓冲池） P(mutex); //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % n; //退出临界区，允许别的进程操作缓冲池 V(mutex); //缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程 V(full); }while(true); } void consumer(){ do { //判断缓冲池中是否有非空的缓冲区（消息） P(full); //判断是否可以进入临界区（操作缓冲池） P(mutex); //从缓冲池中取出消息 nextc = buffer[out]; //移动出队指针 out = (out + 1) % n; //退出临界区，允许别的进程操作缓冲池 V(mutex); //缓冲池中空缓冲区数量加1，可以唤醒等待的生产者进程 V(empty); //消费消息 consumer the item in nextc; ... }while(true); } 通过上面的伪代码，我们可以看到，在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对的出现，并且要出现在同一个程序中；对于用于控制进程同步的信号量full和empty，其P、V操作也必须要成对的出现，但他们分别处于不同的程序之中。还有比较重要的就是，每个程序中的多个P操作顺序不能颠倒，比如说生产者进程，应先执行对资源信号量的P操作–P(empty)，再执行对互斥信号量的P操作–P(mutex)，否则可能会因为持有了互斥锁，但是没有空闲的缓冲区而导致生产者进程阻塞，但是别的进程又无法进入临界区，导致进程发生死锁。 下面给出对应的Java 多线程的实现，为了简单，临界缓冲池我使用了一个长度为50的list来模拟，代码如下： /** * 记录型信号量 */ static final Semaphore mutex = new Semaphore(1); static List buffer = new ArrayList(); static final Semaphore empty = new Semaphore(50); static final Semaphore full = new Semaphore(0); //数据定义 static Integer count = 0; static class Producer extends Thread { Producer(String name) { super.setName(name); } @Override public void run() { do { try { //判断缓冲池中是否仍有空闲的缓冲区 empty.acquire(); //判断是否可以进入临界区（操作缓冲池） mutex.acquire(); log.info("生产了一条消息：【{}】", count); //向缓冲池中投放消息 buffer.add(count++); //Thread.sleep(1000); //释放资源 full.release(); mutex.release(); } catch (InterruptedException e) { log.error("生产消息时产生异常！"); } } while (true); } } static class Consumer extends Thread { Consumer(String name) { super.setName(name); } @Override public void run() { do { try { //判断缓冲池中是否仍有空闲的缓冲区 full.acquire(); //判断是否可以进入临界区（操作缓冲池） mutex.acquire(); log.info("消费了一条消息：【{}】", buffer.remove(0)); //Thread.sleep(1000); empty.release(); mutex.release(); } catch (InterruptedException e) { log.error("消费消息时产生异常！"); } } while (true); } } public static void main(String[] args) { //测试 Producer p1 = new Producer("p1"); Producer p2 = new Producer("p2"); Consumer c1 = new Consumer("c1"); Consumer c2 = new Consumer("c2"); p1.start(); p2.start(); c1.start(); c2.start(); } 5.使用AND型信号量解决生产者-消费者问题 对于AND型信号量，我们就不做过多的说明了，我们直接给出生产者-消费者问题的伪代码解决，也没有什么变化，主要是信号量申请部分： ... //定义信号量并初始化 void producer(){ do { //生产者产生一条消息 producer an item nextp; ... //判断缓冲池中是否仍有空闲的缓冲区&&是否可以进入临界区 Swait(empty, mutex); //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % n; //退出临界区&&消息数量加1，可以唤醒等待的消费者进程 Ssignal(mutex, full); }while(true); } void consumer(){ do { //判断缓冲池中是否有消息&&是否可以进入临界区 Swait(full, mutex); //从缓冲池中取出消息 nextc = buffer[out]; //移动出队指针 out = (out + 1) % n; //退出临界区&&缓冲池中空缓冲区数量加1，可以唤醒等待的生产者进程 Ssignal(mutex, empty); //消费消息 consumer the item in nextc; ... }while(true); } 对应的Java代码实现可以参看我的另一篇博文。 6.使用信号量集解决生产者-消费者问题 信号量集是对AND型型号量的一次扩展，其代码不同的就在于wait操作可以一次申请多个资源和可以设置资源分配下限，下面是伪代码： ... //定义信号量并初始化 void producer(){ do { producer an item nextp; ... //判断缓冲池中是否仍有空闲的缓冲区&&是否可以进入临界区 Swait(empty, 1, 1, mutex, 1, 1); //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % n; //退出临界区&&消息数量加1，可以唤醒等待的消费者进程 Ssignal(mutex, 1, full, 1); }while(true); } void consumer(){ do { //判断缓冲池中是否有消息&&是否可以进入临界区 Swait(full, 1 ,1 , mutex, 1, 1); //从缓冲池中取出消息 nextc = buffer[out]; //移动出队指针 out = (out + 1) % n; //退出临界区&&消息数量减1，可以唤醒等待的生产者进程 Ssignal(mutex, 1, empty, 1); //消费消息 consumer the item in nextc; ... }while(true); } 对应的Java代码实现可以参看我的另一篇博文。 7.使用管程解决生产者-消费者问题 对管程，我们在前面的文章中详细的进行了介绍，在这里也使用管程来解决实际的问题，伪代码如下(我们对于管程内部的过程进行简单的描述)： Monitor ProducerConsumer { intem buffer[N]; int in=0,out=0; condition notempty,notfull;//条件变量 非空和非满 int count=0;//缓冲区中消息的数量 //放消息的过程 void put(item x){ //如果缓冲池满了，则将线程阻塞到notfull中 if(count >= N){ cwait(notfull); } //向缓冲池中投放消息 buffer[in] = nextp; //移动入队指针 in = (in + 1) % N; //缓冲区中消息加一 count++; //唤醒因为没消息消费阻塞的消费者线程 signal(notempty); } //取消息的过程 void get(item x){ //如果缓冲池为空，则将线程阻塞到notempty中 if(count do { //生产者产生一条消息 producer an item nextp; ... PC.put(nextp);//将消息放入到缓冲池中 }while(true); } void consumer(){ item x; do { PC.get(x);//从缓冲池中取出消息 consumer the item in nextc;//消费消息 ... }while(true); } 对应的Java代码实现可以参看我的另一篇博文。 又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。 本文的所有java代码都已通过测试，对其中有什么疑惑的，可以评论区留言，欢迎你的留言与讨论；另外原创不易，如果本文对你有所帮助，还请留下个赞，以表支持。 如有兴趣，还可以查看我的其他几篇博客，都是OS的干货（目录），喜欢的话还请点赞、评论加关注_。 参考文章列表： 1.进程同步机制-----为进程并发执行保驾护航 2.Java并发编程（JUC）模拟AND型信号量 3.Java并发编程（JUC）模拟信号量集 4.Java并发编程模拟管程（霍尔Hoare管程、汉森Hansan管程、MESA管程) 5.操作系统武功修炼心法 6.经典进程同步问题----哲学家进餐问题详解 7.经典进程同步问题----读者-写者问题详解 |
【本文地址】